In high-speed packet switching networks, several classes of traffic share the common resources of the network. Multimedia services such as text, image, voice and video generate traffic at widely varying rates. The traffic characteristics of such different sources, moreover, vary dramatically over time. The transport network must nevertheless guarantee a bandwidth and a quality of service to each connection regardless of these differences. Managing the available bandwidth to avoid congestion and to provide such guaranteed Grades of Service (GOS) for connections with potentially dramatic differences in their statistical behavior is therefore of extreme importance in such networks. For example, while data traffic can usually be slowed down in order to cope with network congestion, real time traffic, such as voice, video or image, has an intrinsic rate determined by external factors; the ability to slow down such sources is usually very limited. Real time traffic therefore requires some level of guaranteed service and hence the allocation of resources for such connections is mandatory. The traffic must be managed, not only to guarantee the availability of resources such as link bandwidth, buffer space, switch capacity, processing resources, and so forth, but also to allocate these resources among the contending traffic streams in a "fair" manner. Network resources are finite, valuable and must be utilized in an optimal manner.
Conventional mechanisms for controlling congestion in a network rely on end-to-end control messages for regulating the flow of traffic. In high speed networks, however, the propagation delays across the network typically dominate the switching and queuing delays. The congestion control feedback messages from the network are therefore usually so outdated that any action taken by the source in response to such messages is too late to resolve the congestion which caused the messages to be initiated in the first place. Conventional end-to-end congestion control mechanisms are simply incapable of deafing realistically with congestion in today's high speed global networks.
Due to the stochastic nature of the packet arrival process, for transitory periods during the connection, the parameters of a source vary from the values determined at the connection setup time. In addition, congestion may arise in the network for brief periods during the course of the connection due to statistical variances in the multiplexing process. It is therefore important not only to regulate the access to the network at the source, but also to regulate traffic flow within the network by buffer management and scheduling functions. These traffic regulation mechanisms enforce the pre-specified classes of service. Since all congestion control procedures used in high speed networks must be available in real time, however, such procedures must be computationally simple.
In order to achieve these goals, the network must regulate the rate of traffic flow from each source into the network. Such rate-based access control mechanisms are preferable over link-by-link flow controls because such access control mechanisms maximize the speed of information transfer over the network. One well-known congestion preventive rate-based access control technique is based on the so-called buffered "leaky bucket" scheme. Such leaky bucket schemes restrict the data transmission, on the average, to the allowable rate, but permit some degree of burstiness diverging from the average. Leaky bucket schemes are disclosed in "Congestion Control Through Input Rate Regulation," by M. Sidi, W-Z. Liu, I. Cidon and I. Gopal, Proceedings of Globecom '89, pages 49.2.1-49.2.5, Dallas, 1989, "The `Leaky Bucket` Policing Method in the ATM (Asynchronous Transfer Mode) Network," by G. Niestegge, International Journal of Digital and Analog Communications Systems, Vol. 3, pages 187-197, 1990, and "Congestion Control for High Speed Packet Switched Networks," by K. Bala, I. Cidon and K. Sohraby, Proceedings of Infocom '90, pages 520-6, San Francisco, 1990. Some of these leaky bucket congestion control schemes involve the marking of packets entering the network to control the procedures used in the network in handling those packets.
In the Bala et al. article, for example, packets leaving a source are marked with one of two different "colors," red and green. Green packets represent traffic that is within the connection's reserved bandwidth, and are guaranteed a prespecified grade of service based on some level of delay and loss probability within the network. The green packets are therefore transmitted at a rate determined at call setup time. Red packets, on the other hand, represent traffic sent over and above the reserved rate and can be viewed as an emergency relief mechanism coming into play during an overload period where the instantaneously offered traffic is above the reserved bandwidth. In other words, the amount of traffic in excess of the allocated bandwidth is marked red and sent into the network, instead of being dropped at the source. Red packets allow a source to exploit any unused network bandwidth in order to improve the efficiency of the statistical multiplexing.
The network nodes operate to store and forward packets. Green and red packets are treated differently, however. The intermediate nodes will discard red packets first at times of congestion, using a low discard threshold. As a result, red packets have a higher loss probability at the intermediate nodes, and, moreover, do not degrade the performance of the green packets to any significant extent.
One leaky bucket mechanism is described in detail in the copending application of the present applicant Ser. No. 07/932,440, filed Aug. 19, 1992, and assigned to applicants' assignee. It is of considerable importance in leaky bucket access control schemes that the red packets do not degrade the performance of the green packets. Moreover, it is also desirable that the red packets make as much use as possible of the available bandwidth on the network. For example, if the amount of red traffic is not controlled, it is possible that the red packets can destructively interfere with each other, resulting in a lower red packet throughput than the network would have otherwise permitted. These problems are of extreme concern in very large national or international networks where traffic is heavy, demand great and the efficiency of the network of paramount importance.